package com.hackerrank.challenges.kcandystore;

import java.util.Scanner;

public class Solution {
	private static int MAX = 1000000000;
	private static int numWays(int N, int K) {
		int p[] = new int[K + 1];
		p[0] = 1;
		for(int i = 1; i <= N; i++) {
			int c[] = new int[K + 1], s = 0;
			for(int j = 0; j <= K; j++) {
				s = (s + p[j]) % MAX;
				c[j] = s;
			}
			p = c;
		}
		return p[K];
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		for(int t = 0; t < T; t++) {
			int N = in.nextInt(), K = in.nextInt();
			System.out.println(numWays(N, K));
		}
	}
}
